package dp

// i和j表示以当前位置结尾的串的最长子序列长度，
// 所以只要当i>j时，取之前算过的为i结尾的最长子序列长度或者
// 以j结尾的子序列长度+1
func lengthOfLIS(nums []int) int {
	dp := make([]int, len(nums))
	for i := range dp {
		dp[i] = 1
	}

	res := dp[0]
	for i := 1; i < len(nums); i++ {
		for j := 0; j < i; j++ {
			if nums[i] > nums[j] {
				dp[i] = max300(dp[i], dp[j]+1)
			}
			if dp[i] > res {
				res = dp[i]
			}
		}
	}
	return res
}

func max300(x, y int) int {
	if x > y {
		return x
	}
	return y
}
